class Solution {
public:
    void SerializeFunction(TreeNode* root, string& str)
    {
        if (root == nullptr)
        {
            str += '#';
            return;
        }
        str += to_string(root->val);
        str += '!';
        SerializeFunction(root->left, str);
        SerializeFunction(root->right, str);
    }
    char* Serialize(TreeNode* root)
    {
        if (root == nullptr)
            return "#";
        string str;
        SerializeFunction(root, str);
        char* res = new char[str.size() + 1];
        strcpy(res, str.c_str());
        return res;
    }
    TreeNode* DeserializeFunction(char** str)
    {
        if (**str == '#')
        {
            (*str)++;
            return nullptr;
        }
        int vaule = 0;
        while (**str != '!' && **str != '\0')
        {
            vaule = vaule * 10 + ((**str) - '0');
            (*str)++;
        }
        TreeNode* root = new TreeNode(vaule);
        if (**str == '\0')
            return root;
        else
            (*str)++;
        root->left = DeserializeFunction(str);
        root->right = DeserializeFunction(str);
        return root;
    }
    TreeNode* Deserialize(char* str)
    {
        if (str == "#")
            return nullptr;
        TreeNode* res = DeserializeFunction(&str);
        return res;
    }
};